package com.nuo.laboratory.dataStructure;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 我的单链表
 *
 * @author LGC
 * @date 2022/3/22 11:04
 */
public class MyLinkedList {


    /**
     * 定义简单链表节点
     */
    static class Node {
        int val;
        Node next;

        Node(int val, MyLinkedList.Node next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 是否成环
     *
     * @param head
     * @return
     */
    public boolean isCycle(Node head) {
        Node a = head;
        Node b = head;
        // 是环状链表
        while (a != null && a.next != null) {
            a = head.next.next;
            b = head.next;
            // 到达第一个相遇点
            if (a == b) {
                return true;
            }
        }

        return false;
    }

    /**
     * 获取入环切入点，无环直接返回空
     *
     * @param head
     * @return
     */
    public Node detectCycle(Node head) {
        Node a = head;
        Node b = head;
        // 是环状链表
        while (a != null && a.next != null) {
            a = head.next.next;
            b = head.next;
            // 到达第一个相遇点
            if (a == b) {
                break;
            }
        }
        // 不是环转链表直接返回
        if (a == null || a.next == null) {
            return null;
        }
        // 其中一个回到头结点，另外一个在第一次相遇点
        a = head;
        // 还未到达切入点，两个都一步一步走，两个相等是就是切入点
        while (a != b) {
            a = a.next;
            b = b.next;
        }
        return a;
    }


    /**
     * 移除倒数第n个节点
     *
     * @param head
     * @param n
     * @return
     */
    public Node removeNthFromEnd(Node head, int n) {
        //删除节点的前一个元素
        Node preNode = head;

        // 计算链表个数
        int size = getSize(head);

        // 删除的是头结节
        if (size - n == 0) {
            head = head.next;
            return head;
        }

        // 删除节点下标  1 2 3 4 5   3
        int delIndex = size - n;

        // 获取删除节点的前一个元素
        for (int i = 0; i < delIndex - 1; i++) {
            preNode = preNode.next;
        }
        // 获取删除节点的后一个元素
        Node delAfterNode = preNode.next.next;
        // 删除节点的前一个元素 的下个结点为 删除节点的后一个元素
        preNode.next = delAfterNode;
        return head;
    }

    public int getSize(Node head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }

    /**
     * 链表反转 利用栈的特性先进后出
     *
     * @param head
     * @return
     */
    public Node reverseList(Node head) {
        Stack<Node> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        // 栈元素为空
        if (stack.isEmpty()) {
            return null;
        }
        // 取出第一个
        Node node = stack.pop();
        // 返回的节点
        Node dummy = node;
        //栈中的结点全部出栈，然后重新连成一个新的链表
        while (!stack.isEmpty()) {
            Node tempNode = stack.pop();
            node.next = tempNode;
            // 指向下一个节点
            node = node.next;
        }
        //最后一个结点就是反转前的头结点，一定要让他的next等于空，否则会构成环
        node.next = null;
        return dummy;
    }


    /**
     * 删除指定值的链表节点
     * 利用单指针循环解决
     */
    public Node removeElements(Node head, int val) {
        if (head == null) {
            return null;
        }
        Node index = head;
        // 处理非头尾节点
        while (index.next != null) {
            if (index.next.val == val) {
                // 删除节点
                index.next = index.next.next;
                // 后面节点是否也存在相同值继续循环
                continue;
            }
            index = index.next;
        }
        // 处理最后节点（或只有一个节点）
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    public Node removeElements1(Node head, int val) {

        Node temp = new Node(0, head);
        Node index = temp;
        // 处理非头尾节点
        while (index.next != null) {
            if (index.next.val == val) {
                // 删除节点
                index.next = index.next.next;

            } else {
                index = index.next;
            }
        }
        // 处理最后节点（或只有一个节点）
        if (head.val == val) {
            head = head.next;
        }
        return index.next;
    }


    /**
     * 是否是回文链表
     * 利用栈后入先出特性翻转链表，如果存在栈的前半段链表节点值不等于原链表前半段链表节点值，说明就不是回文链表
     */
    public boolean isPalindrome(Node head) {
        if (head == null) {
            return false;
        }
        // 节点个数
        Stack<Integer> stack = new Stack<>();
        int size = 0;
        Node temp = head;
        while (temp != null) {
            size++;
            stack.push(temp.val);
            temp = temp.next;
        }
        // 节点个数除以2，一半的节点数
        size = size >> 1;

        while (size > 0) {
            if (stack.pop() != head.val) {
                return false;
            }
            head = head.next;
            size--;
        }
        return true;
    }


    /**
     * 奇偶链表 下标为奇数的派前面，下标为偶数的在后面 顺序输出
     * 利用快慢指针来解决
     * 输入: head = [2,1,3,5,4,6]
     * 输出: [2,3,4,1,5,6]
     */
    public Node oddEvenList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 奇数
        Node slow = head;
        // 偶数
        Node fast = head.next;
        while (fast != null && fast.next != null) {
            // 原偶数的下一个奇数
            Node target = fast.next;

            // 偶数的下一个元素
            fast.next = fast.next.next;
            fast = fast.next;

            // 下一个奇数的下一个元素 = 原奇数的下一个偶数节点
            target.next = slow.next;
            // 奇数的下一个元素
            slow.next = target;
            slow = slow.next;

        }
        return head;
    }


    public Node oddEvenList1(Node head) {
        // head = [2,1,3,5,4,6]
        if (head == null) {
            return null;
        }
        // 奇 引用head 重新排序
        Node odd = head;
        Node newHead = head.next;
        // 偶 引用新的head 重新排序
        Node even = newHead;

        while (even != null && even.next != null) {
            odd = even.next;
            odd = odd.next;
            even = odd.next;
            even = even.next;
        }
        // 连接起来 奇的下一个节点后面为偶
        odd.next = newHead;
        return head;
    }


    // 1 3 4 6
    public Node oddEvenList2(Node head, int val) {
        Node temp = new Node(0, head);
        Node index = temp;
        while (index.next != null) {
            if (index.next.val == val) {
                index.next = index.next.next;
            }else{
                index = index.next;
            }
        }


        return head;
    }


    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(2);
        list.add(1);
        list.add(3);
        list.add(5);
        list.add(4);
        list.add(6);
        System.out.print("排序前：" + list);
        System.out.println("++++++++++++++");
        System.out.print("排序后：");
    }


    Node head;
    int size = 0;

    /**
     * 获取链表中第 index 个节点的值。如果索引无效，则返回-1
     */
    public int get(int index) {
        if (index < 0 || index >= size || head == null) {
            return -1;
        }
        Node temp = this.head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp.val;
    }

    /**
     * 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
     */
    public void addAtHead(int element) {
        Node node = new Node(element, this.head);
        this.head = node;
        size++;
    }

    /**
     * 将值为 val 的节点追加到链表的最后一个元素
     */
    public void addAtTail(int val) {
        if (size == 0) {
            this.head = new Node(val, null);
            size++;
        } else {
            // 循环到当前链表尾节点
            Node temp = this.head;
            while (temp.next != null) {
                temp = temp.next;
            }
            // 创建一个尾节点，赋值到当前链表尾节点下一个节点
            temp.next = new Node(val, null);
            size++;
        }
    }

    /**
     * 在链表中的第index个节点之前添加值为val 的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。
     * 如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点
     */
    public void addAtIndex(int index, int val) {
        // 下标超出当前范围直接返回
        if (index > this.size) {
            return;
        }
        // 下标小于等于0 在头部添加
        if (index <= 0) {
            addAtHead(val);
            return;
        }
        // 下标等于链表大小 在尾部添加
        if (index == this.size) {
            addAtTail(val);
            return;
        }
        // 循环出  1 2 3
        Node temp = this.head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        // 创建插入的节点，
        Node insertNode = new Node(val, temp.next);
        temp.next = insertNode;
        size++;
    }

    /**
     * 如果索引 index 有效，则删除链表中的第 index 个节点
     */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= this.size) {
            return;
        }
        if (index == 0) {
            if (size != 1) {
                Node temp = this.head.next;
                this.head = temp;
                size--;
                return;
            } else {
                this.head = null;
                size--;
                return;
            }
        }

        Node temp = this.head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp.next;
        }
        Node deleteNode = temp.next;
        temp.next = deleteNode.next;
        size--;
    }


}


